// 贪心算法

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) 
    {
        int n = intervals.size();

        return n - intervalSch(intervals);
    }

    // 区间调度算法-计算最多有多少个不相交的区间
    int intervalSch(vector<vector<int>>& intervals)
    {
        if(intervals.empty())
            return 0;

        //排序 - 按end值升序排列
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[1] < b[1];});

        int count = 1; // 最少有一个

        int xEnd = intervals[0][1]; // 此时xEnd就是end值最小的区间

        for(const auto& interval : intervals)
        {
            int begin = interval[0];
            if(begin >= xEnd)
            {
                count++;
                // 找到下一个选择的区间了
                xEnd = interval[1];
            }
        }

        return count;
    }
};


class Solution {
public:
    bool canJump(vector<int>& nums) 
    {
        int n = nums.size();

        int fastest = 0;

        for(int i = 0; i < n - 1; i++)
        {
            fastest = max(fastest, i + nums[i]);

            if(fastest <= i)
                return false;
        }

        return fastest >= n - 1;
    }
};

class Solution {
public:
    int jump(vector<int>& nums) 
    {
        // i和end 标记了所有选择的跳跃距离，fastest标记了[i,end]选择中能抬哦到的的最远距离
        int n = nums.size();

        int end = 0;
        int fastest = 0;
        int jumps = 0;

        for(int i = 0; i < n - 1; i++)
        {
            fastest = max(fastest, i + nums[i]);

            if(i == end)
            {
                jumps++;
                end = fastest;
            }
        }

        return jumps;
    }
};



// 二叉树的最大深度
// 方法一：遍历二叉树求得答案-用外部变量记录每个节点的深度，取最大值即可

int res = 0; // 记录最大深度

int depth = 0; // 记录遍历到的节点的深度

// 主函数
int maxDepth(TreeNode* root)
{
        traverse(root);

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) 
    {
        int n = intervals.size();

        // 红点表示会议开始时间，绿点表示会议结束时间
        vector<int> begin(n);
        vector<int> end(n);

        for(int i = 0; i < n; i++)
        {
            begin[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }

        sort(begin.begin(), begin.end(), [](const int a, const int b){return a < b;});
        sort(end.begin(), end.end(), [](const int a, const int b) {return a < b;});

        int count = 0; // 计数
        int res = 0, i = 0, j = 0; // 双指针技巧

        while(i < n && j < n)
        {
            if(begin[i] < end[j])
            {
                // 扫描到一个红色节点
                count++;
                i++;
            }
            else
            {
                // 扫描到一个绿色节点
                count--;
                j++;
            }

            res = max(res, count);
        }

        return res;
    }
}
;

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) 
    {
        int n = intervals.size();

        // 红点表示会议开始时间，绿点表示会议结束时间
        vector<int> begin(n);
        vector<int> end(n);

        for(int i = 0; i < n; i++)
        {
            begin[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }

        sort(begin.begin(), begin.end(), [](const int a, const int b){return a < b;});
        sort(end.begin(), end.end(), [](const int a, const int b) {return a < b;});

        int count = 0; // 计数
        int res = 0, i = 0, j = 0; // 双指针技巧

        while(i < n && j < n)
        {
            if(begin[i] < end[j])
            {
                // 扫描到一个红色节点
                count++;
                i++;
            }
            else
            {
                // 扫描到一个绿色节点
                count--;
                j++;
            }

            res = max(res, count);
        }

        return res;
    }
};


class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int time) 
    {
        if(time == 0)
            return 0;

        // 起点按照升序排列，起点相同的按照降序排列
        sort(clips.begin(), clips.end(), [](vector<int>& a, vector<int>& b)
        {
            if(a[0] == b[0])
            {
                return a[1] > b[1];
            }
            return a[0] < b[0];
        });

        // 记录选择的短视频个数
        int res = 0;

        int curEnd = 0, nextEnd = 0;
        int i = 0, n = clips.size();

        while(i < n && clips[i][0] <= curEnd)
        {
            // 在第res个视频的区间内贪心选择下一个视频
            while(i < n && clips[i][0] <= curEnd)
            {
                nextEnd = max(nextEnd, clips[i][1]);
                i++;
            }

            // 找到下一个视频，更新curEnd
            res++;
            curEnd = nextEnd;
            if(curEnd >= time)
                // 已经可以拼出区间[0, T]
                return res;
        }

        return -1;
    }
};



